The present invention relates to a method and device for recognising, with error tolerance, a set of bit patterns in a bit stream, said set being limited with respect to the number of bit patterns and size. This application is based on application No. 9600831-3 filed in Sweden, the content of which is incorporated hereinto by reference.
In many areas where digital transmission of data is used, there is a need to recognise one or a certain number of so-called bit patterns or data words in the transmitted quantity of data. These data words can for instance be so-called synchronising words. Synchronising words are special data words which are used in order to synchronise a transmitter with a receiver which are not synchronised with one another. Synchronising of a transmitter and a receiver has to be performed in order for the receiver to know where the information starts and ends and in order to be able to reliably transmit the information between these. A transmitter and a receiver can be synchronised in many different ways, but a cheap and relatively simple way is by making use of synchronising words.
Transmission of data between two units can occur either in parallel or in series. By series transmission is meant that one amount of information is transferred at a time via a single data conductor where a quantity of information can be anything from one single binary bit (0 or 1) to symbols for example. By parallel transmission is normally meant that one larger quantity of information is transmitted each time via a number of parallel data conductors, typically multiples of eight bits. Conversion between the two manners of transmission can be done by using series to parallel converters and parallel to series converters.
Bit pattern detection can be made on a predetermined number of consecutive bits or on bits which are dispersed in a bit stream which is accessible serially. A candidate bit pattern is formed from the bit stream, the candidate bit pattern having the predetermined number of bits which the bit pattern has that it is wished to detect. Normally it is desirable that bit pattern detection occurs over the whole or parts of the bit stream, whereby new candidate bit patterns with the predetermined number of bits have to be formed. Candidate bit patterns are formed by extraction from the bit stream. New candidate bit patterns are suitably formed with the same speed as the bit speed in the bit stream by the bit stream being displaced by one bit position for each subsequent extraction of a new candidate bit pattern. This can also be referred to as the bit pattern detection being displaced one bit position in the bit stream.
The desire to recognise certain bit patterns is often combined with a desire that the recognition should be as fast as possible and moreover with as few operations as possible.
A known solution is based on using an XOR-construction. The XOR-construction compares each candidate bit pattern of a received bit stream with each and every bit pattern which it is wished to recognise. A bit pattern is viewed as being detected when the result of an XOR-operation is equal to zero. The solutions using XOR-constructions result in very high capacity requirements since all XOR-operations and comparisons to zero have to be fitted into a time interval which corresponds to the bit speed of the bit stream. Moreover, all XOR-operations and comparisons to zero have to be repeated for each candidate bit pattern which is formed from the bit stream. Given the aforementioned requirement on the speed, this puts extremely large requirements on the hardware.
A solution which requires many operations and where each operation requires many part-operations suffers from the fact that the clock frequency with which the hardware has to be clocked is necessarily very high. If the hardware's processing speed, which relates to its clock frequency, is not sufficiently high, there will not be time to carry out all the necessary operations and part-operations in an available time period. There is a theoretical and practical upper limit for how high a device's clock frequency can be, which gives an upper limit to how many operations and part-operations the hardware/device can carry out within a time period. A device which is clocked with a high clock frequency also unavoidably draws a large current, a feature which can be a large problem in mobile and, for example, battery-operated devices.
The XOR-method is suitable really only for transmission methods which have a low bit speed and a low error intensity, since the method is extremely calculation-intensive. Due to the fact that the XOR-method is calculation-intensive, the method can only cope with comparisons for those bit patterns which one is trying to find, even when using transmission methods which have a low transmission speed. The XOR-method is therefore not error tolerant (fault tolerant). In order to achieve error tolerance, i.e. to be able to detect bit patterns with a corruption (one or several bit errors), the aforementioned XOR-operations and comparisons have to be increased with XOR-operations and comparisons against every "corruption" (error) which is to be included in the detection. An increase in the number of XOR-operations and comparisons additionally have to be able to be carried out within the same available time period. An increase in the number of operations which need to be carried out within a given time period puts additional speed requirements on the hardware carrying it out. This leads to the included components being more expensive and to a higher current consumption, if it is indeed at all possible to carry this out.
A number of mobile telephone systems make use of TDMA (Time Division Multiple Access), for example PDC (Pacific or Personal Digital Cellular). In TDMA systems there is a strong desire to be able to combine the above-mentioned requirements on the speed with error tolerance during searching for bit patterns, for example synchronising words, in a bit stream. Error tolerance is a particularly important characteristic in radio-based information transmission systems since radio-based transmission is far from ideal. Transmission of information in TDMA systems, inter alia data and synchronising words occurs in allotted time slots and, by finding the synchronising words, the receiver can determine where in the time slots the information is located.
In U.S. Pat. No. 4,847,877 a device is described which is intended for detection of a bit pattern in a bit stream. The method first tries to detect part-quantities of the bit pattern which is being searched for in the bit stream, by comparing part candidate bit patterns from the bit stream with each acceptable part-quantity separately. Then, upon detection of an acceptable part-quantity, each separate bit in the bit stream is compared with the remaining bits in the searched bit pattern, whereby counters count the number of accepted comparisons. It can be seen as a disadvantage with this device that it requires a large number of operations and part-operations for the bit pattern detection and that it probably does not allow, in any greater degree, error tolerance in a simple manner.